import java.util.Arrays;
import java.util.Comparator;

/**
 * @作者 zxy
 * @时间 2023-04-18 16:27
 * @说明 179. 最大数
 * 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
 * 注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
 * 示例 1：
 * 输入：nums = [10,2]
 * 输出："210"
 */
public class Solution {
    public static void main(String[] args) {
        new Solution().largestNumber(new int[]{3, 30, 34, 5, 9});
        new Solution().largestNumber(new int[]{34323, 3432});
    }

    /**
     * 执行用时： 3 ms, 在所有 Java 提交中击败了91.52% 的用户
     * 内存消耗： 39.6 MB, 在所有 Java 提交中击败了95.22%的用户
     * @param nums
     * @return
     */
    public String largestNumber(int[] nums) {
        String[] strings = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strings[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                int max1 = Integer.MIN_VALUE;
                int max2 = Integer.MIN_VALUE;
                for (int i = 0; i < Math.min(o1.length(), o2.length()); i++) {
                    max1 = Math.max(max1, o1.charAt(i));
                    max2 = Math.max(max2, o2.charAt(i));
                    if (o1.charAt(i) != o2.charAt(i)) return o1.charAt(i) - o2.charAt(i);
                }
                if (o1.length() > o2.length()) {
                    if (o1.charAt(o2.length()) > o2.charAt(o2.length() - 1) && o1.charAt(o2.length()) >= max2)
                        return 1;
                    else return -1;
                } else if (o1.length() < o2.length()) {
                    if (o2.charAt(o1.length()) > o1.charAt(o1.length() - 1) && o2.charAt(o1.length()) >= max1)
                        return -1;
                    else return 1;
                } else return 0;
            }
        });
        StringBuilder sb = new StringBuilder();
        for (int i = strings.length - 1; i >= 0; i--) {
            sb.append(strings[i]);
        }
        if (new String(sb).replace("0", "").equals("") && sb.length() > 1)
            sb = new StringBuilder("0");
        return String.valueOf(sb);
    }
}
